/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2022-10-11
 * Time: 12:59
 */

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class Main {
    public ListNode partition(ListNode head, int x) {
        if(head==null||head.next==null){
            return head;
        }
        ListNode minHead=null;
        ListNode minTail=null;
        ListNode maxHead=null;
        ListNode maxTail=null;
        ListNode cur=head;
        while(cur!=null)
        {
            ListNode node=new ListNode(cur.val);
            if(cur.val<x){
                if(minHead==null){
                    minHead=node;
                    minTail=node;
                }else{
                    minTail.next=node;
                    minTail=node;
                }
            }else{
                if(maxHead==null){
                    maxHead=node;
                    maxTail=node;
                }else{
                    maxTail.next=node;
                    maxTail=node;
                }
            }
            cur=cur.next;
        }
        if(minHead==null){
            return maxHead;
        }else{
            minTail.next=maxHead;
            return minHead;
        }
    }
}
